import data.Graphe;
import data.History;
import data.Sommet;


public class GrapheSearch {
	public boolean solved=false;



	public int dfs2(Graphe g, Sommet s, int bound,int provenance,History h){
		if (g.estimationDistance(s)==0){
			solved=true;
			return bound;
		}
		int new_bound=java.lang.Integer.MAX_VALUE;
		if (s.zero>3&&!(provenance==1)){
			int b=0;
			g.haut(s);
			h.add(s);
			if(1+s.estimation<=bound){
				b=1+dfs2(g,s,bound-1,3,h);


			}else{
				b=1+s.estimation;

			}
			if (solved) {return b;}
			h.remove();
			new_bound=Math.min(b, new_bound);
			g.bas(s);


		}
		if (s.zero<12&&!(provenance==3)){
			int b=0;
			g.bas(s);
			h.add(s);
			if(1+s.estimation<=bound){
				b=1+dfs2(g,s,bound-1,1,h);
			}else{
				b=1+s.estimation;

			}
			if (solved) {return b;}

			h.remove();
			new_bound=Math.min(b, new_bound);
			g.haut(s);
		}
		if (!(s.zero % 4==3)&&!(provenance==2)){
			int b=0;
			g.droite(s);
			h.add(s);
			if(1+s.estimation<=bound){
				b=1+dfs2(g,s,bound-1,4,h);
			}else{
				b=1+s.estimation;

			}
			if (solved) {return b;}

			h.remove();
			new_bound=Math.min(b, new_bound);
			g.gauche(s);
		}
		if (!(s.zero % 4==0)&&!(provenance==4)){
			int b=0;
			g.gauche(s);
			h.add(s);
			if(1+s.estimation<=bound){
				b=1+dfs2(g,s,bound-1,2,h);
			}else{
				b=1+s.estimation;

			}
			if (solved) {return b;}
			h.remove();

			new_bound=Math.min(b, new_bound);
			g.droite(s);
		}

		return new_bound;
	}
	
	
	public void IDA2(Graphe g,Sommet s){

		int bound=g.estimationDistance(s);

		History h=new History();
		while(!(solved)){
			h=new History();
			h.add(s);
			bound=dfs2(g,s,bound,0,h);


		}
		System.out.println("OK "+bound);
		for (int i=h.liste.size()-1;i>=0;i=i-1){
			int[] t =h.liste.get(i);
			for (int j=0;j<16;j=j+1){
				System.out.print(t[j]+" ");
			}
			System.out.println();
		}
	}
}






